package com.company.Demo;

import java.util.HashMap;
import java.util.Scanner;

public class ZSYYJS {
    static int count = 0;
    public static void main(String[] args) {
        String s1 = "catapult";
        String s2 = "cat";

        HashMap<Character,Integer> map = new HashMap<>();

        char[] arr = s2.toCharArray();
        for(int i =0;i<arr.length;i++){
            map.put(arr[i],0);
        }
        char[] brr = s1.toCharArray();
        StringBuilder stringBuilder = new StringBuilder();
        for(int i =0;i<brr.length;i++){
            if(map.containsKey(brr[i])){
                stringBuilder.append(brr[i]);
            }
        }
        String s = stringBuilder.toString();//catat
        dfs(s,s2,new StringBuilder(),0,0);
        System.out.println(count);
    }

    public static void dfs(String s1,String s2,StringBuilder stringBuilder,int index,int indexs2){
        if(stringBuilder.length()==s2.length()&&stringBuilder.toString().equals(s2)){
            count++;
            System.out.println(stringBuilder.toString());
            return;
        }
        if(stringBuilder.length()>=s2.length()){
            return;
        }
        for(int i =index; i<s1.length();i++){
            stringBuilder.append(s1.charAt(i));
            dfs(s1,s2,stringBuilder,i+1,indexs2+1);
            stringBuilder.deleteCharAt(stringBuilder.length()-1);
        }
    }
}
